tags:
- DSAL4. Group Anagrams (Star)
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
strs = ["eat", "tea", "tan", "ate", "nat", "bat"][["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]Example 2:
strs = [""][[""]]为了解决这道题，键值对肯定少不了。为了快速插入和查询，我选择使用 std::unordered_map。由于我们需要对字符串数组进行分类，并输出分组后的结果。和 L2. Valid Anagram > Solution - 1 类似的思路，这里我们先对字符串数组中的每个字符串进行排序，将排序后的字符串作为键，排序前的字符串作为值。利用这种键值对关系，我们可以将所有键值对加入到 std::unordered_map 中。
这样，每一个键都会对应一组具有相同字符组合的字符串（share a same anagram）。通过遍历 std::unordered_map 中的值，即可输出分类后的字符串数组。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
class mySolution{
public:
std::vector<std::vector<std::string>> groupAnagrams(const std::vector<std::string>& anagrams) {
std::unordered_map<std::string, std::vector<std::string>> map;
for(auto str : anagrams){
std::string sorted_str = str;
std::sort(sorted_str.begin(), sorted_str.end());
map[sorted_str] .push_back(str);
}
std::vector<std::vector<std::string>> groupedAnagrams;
for(auto entry : map){
groupedAnagrams.push_back(entry.second);
}
return groupedAnagrams;
}
};
int main() {
std::vector<std::string> anagrams{"eat", "tea", "tan", "ate", "nat", "bat"};
mySolution solution;
std::vector<std::vector<std::string>> grouped_Anagrams = solution.groupAnagrams(anagrams);
for(auto group : grouped_Anagrams){
for(auto str : group){
std::cout<< str << ", ";
}
std::cout << std::endl;
}
return 0;
}